package problem;

import java.util.*;

public class S_133 {
    //克隆图
    /*给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。
    图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。*/

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

    class Solution {
        public Node cloneGraph(Node node) {
            Map<Node,Node> map=new HashMap<>();
            return dfs(node,map);
        }
        //返回根据node克隆出来的结点
        public Node dfs(Node node,Map<Node,Node> map){
            if(node==null) return null;
            if(map.containsKey(node)) return map.get(node);
            Node clone=new Node(node.val,new ArrayList<>());
            map.put(node,clone);
            for(Node n:node.neighbors){
                clone.neighbors.add(dfs(n,map));
            }
            return clone;
        }
    }

    class Solution1{
        public Node cloneGraph(Node node){
            if(node==null) return null;
            Queue<Node> queue=new LinkedList<>();
            Map<Node,Node> map=new HashMap<>();
            Node clone=new Node(node.val,new ArrayList<>());
            map.put(node,clone);
            queue.add(node);
            while(!queue.isEmpty()){
                Node poll = queue.poll();
                for(Node n:poll.neighbors){
                    if(!map.containsKey(n)){
                        map.put(n,new Node(n.val,new ArrayList<>()));
                        queue.add(n);
                    }
                    map.get(poll).neighbors.add(map.get(n));
                }
            }
            return node;
        }
    }
}
